//
// Created by zhou on 2021/10/24.
//
//先使用深度优先搜索
//使用广度优先搜索
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
class Solution {
public:
    const int dx[4]={0,0,-1,1};
    const int dy[4]={1,-1,0,0};
    void DFS(vector<vector<int>>& grid,int sr,int sc,int curColor,int newColor,int & m){
        if(grid[sr][sc]==curColor){
            grid[sr][sc]=newColor;
            m+=1;
        }
        for(int i=0;i<4;i++){
            int mx=dx[i]+sr;
            int my=dy[i]+sc;
            if(mx>=0&&mx<grid.size()&&my>=0&&my<grid[0].size()&&grid[mx][my]==curColor){
                DFS(grid,mx,my,curColor,newColor,m);
            }
        }
    }
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int curColor=1;
        int newColor=0;
        int maxarea=0;
        for(int i=0;i<grid.size();i++){
            for(int j=0;j< grid[0].size();j++){
                if(grid[i][j]==curColor){
                    int m=0;
                    DFS(grid,i,j,curColor,newColor,m);
                    maxarea=max(maxarea,m);
                }
            }
        }
        return maxarea;
    }
    void BFS(vector<vector<int>>& grid,int sr,int sc,int curcolor,int newColor,int & m){
//        int curcolor=grid[sr][sc];
        if(grid[sr][sc]==newColor)return;
        queue<pair<int,int>> que;
        que.emplace(sr,sc);
        while(!que.empty()) {
            int x = que.front().first;
            int y = que.front().second;
            if(grid[x][y]==curcolor){grid[x][y] = newColor;m++;}
            que.pop();

            for (int i = 0; i < 4; i++) {
                int mx = x + dx[i], my = y + dy[i];
                if (mx >= 0 && mx < grid.size() && my >= 0 && my < grid[0].size() && grid[mx][my] == curcolor) {
                    que.emplace(mx, my);

                }
            }
        }

    }
    int maxAreaOfIsland1(vector<vector<int>>& grid){
        int curColor=1;
        int newColor=0;
        int maxarea=0;
        for(int i=0;i<grid.size();i++){
            for(int j=0;j< grid[0].size();j++){
                if(grid[i][j]==curColor){
                    int m=0;
                    BFS(grid,i,j,curColor,newColor,m);
                    maxarea=max(maxarea,m);
                }
            }
        }
        return maxarea;
    }
};

int main(){
    Solution solution;
    vector<vector<int>> grid={
            {0,0,1,1,0},
            {1,1,0,0,0},
            {0,0,1,1,1},
            {1,1,1,1,0},
            {0,0,1,1,1}
    };
//    cout<<solution.maxAreaOfIsland(grid);
    cout<<endl;
    cout<<solution.maxAreaOfIsland1(grid);
}
